/**
 * 781. 森林中的兔子
 * https://leetcode-cn.com/problems/rabbits-in-forest/
 */
public class Solutions_781 {
    public static void main(String[] args) {
//        int[] answers = {1, 1, 2};  // output: 5
//        int[] answers = {10, 10, 10};  // output: 11
//        int[] answers = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10};  // output: 22
        int[] answers = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10};  // output: 11

        int result = numRabbits(answers);
        System.out.println(result);
    }

    /**
     * 解题思路：数学思想
     * 要使兔子的数量最少
     * 那么就需要使用 answer 相同的，组合在一起
     * 例：
     * 3 个 2，即 3 个兔子都说：还有 2 个兔子和自己有相同的颜色
     * 通过式子计算得到最少有 3 只兔子：Math.ceil(3 / (2 + 1.0)) * (2 + 1) = 3
     *
     * 5 个 2，即 5 个兔子都说：还有 2 个兔子和自己有相同的颜色
     * 通过式子计算得到最少有 6 只兔子：Math.ceil(5 / (2 + 1.0)) * (2 + 1) = 6
     * 即：5 个都回答了 '2' 的兔子中，其中 3 个可以是一种颜色，即自己本身再加其他的 2 只兔子
     *    还剩下 2 只兔子，但是这 2 只兔子都说还有 2 只兔子有相同颜色，
     *    那么最少还有 2 + 1 = 3 只兔子
     */
    public static int numRabbits(int[] answers) {
        int[] counts = new int[1000];
        // 统计次数
        for (int a : answers) {
            counts[a] ++;
        }
        int res = 0;
        // 计算
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] > 0) {
                // 需要向上取整
                int j = (int) Math.ceil(counts[i] / (i + 1.0)) * (i + 1);
                res += j;
            }
        }
        return res;
    }
}
